EM算法

2023-10-09 14:06| 来源: 网络整理| 查看: 265

EM算法

原文链接：https://www.cnblogs.com/zdz8207/p/DeepLearning-em-gosimix.html

本文经过一定修改，个人认为原文中存在符号混用情况，对Q函数的角码使用不太清晰，容易晕

假设训练集 $\{x^{(1)},x^{(2)},...,x^{(m)}\}$ 是由m个独立的样本构成。我们的目的是要对 $p(x,z)$ 概率密度函数进行参数估计。它的似然函数为：

$\begin {aligned}l(\theta)&=\underset{i=1}{\overset{m}{\sum}}log\;p(x,\theta)\\ &=\underset{i=1}{\overset{m}{\sum}}log\underset{z}{\sum}p(x,z;\theta) \end{aligned}$

然而仅仅凭借似然函数，无法对参数进行求解。因为这里的随机变量 $z^{(i)}$ 是未知的。

EM算法提供了一种巧妙的方式，可以通过逐步迭代逼近最大似然值。下面就来介绍下EM算法：

假设对于所有j， $Q_{j}$ 为随机变量 $z^{(i)}$ 的第j个分布函数(在此时i为固定量即： $\sum_{Z}Q_{j}(z)=1,Q_{j}(z)\ge0$ 。那么：

$\begin{aligned}l(\theta)&=\underset{i}{\sum}log \; p(x^{(i)};\theta)\\ &=\underset{i}{\sum}log\underset{z^{(i)}}{\sum}p(x^{(i)},z^{(i)};\theta)\quad\quad\quad\quad &(1)\\&=\underset{i}{\sum}log\underset{z^{(i)}}{\sum}Q_{j}(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{j}(z^{(i)})}&(2)\\ &\ge \underset{i}{\sum}\underset{z^{(i)}}{\sum}Q_{j}(z^{(i)})log\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{j}(z^{(i)})}&(3) \end{aligned}$

其中第（2）步至第（3）步的推导就使用了Jensen不等式。其中：f(x)=log x， $f''(x)=-\frac{1}{x^{2}}<0$ ，因此为凸函数； $\underset{^{(j)}}{\sum}Q_{j}(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{j}(z^{(i)})}$ 表示随机变量为 $Q_{j}(z^{(i)})$ 概率分布函数为 $\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{j}(z^{(i)})}$ 的期望。因此有：

$f(\underset{z^{(i)}\sim Q_{i}}{E}[\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}])\ge \underset{z^{(i)}\sim Q_{j}}{E}[f(\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{j}(z^{(i)})})]$

这样，对于任意分布 $Q_{j}$ ，（3）都给出了 $l(\theta)$ 的一个下界。如果我们现在通过猜测初始化了一个 $\theta$ 的值，我们希望得到在这个特定的 $\theta$ 下，更紧密的下界，也就是使等号成立。根据Jensen不等式等号成立的条件，当 $\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{j}(z^{(i)})}$ 为一常数时，等号成立。即：

$\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{j}(z^{(i)})} =c$

由上式可得 $p(x^{(i)},z^{(i)};\theta)=cQ_{j}(z^{(i)})$ ，又 $\sum_{j}Q_{j}(z)=1$ ，因此 $p\left(x^{(i)} ; \theta\right)=c$ 。再由上式可得：

$\begin {aligned}Q_{j}(z^{(i)})&=\frac{p(x^{(i)},z^{(i)};\theta)}{\sum_{z}{p(x^{(i)},z;\theta)}}\\&=\frac{p(x^{(i)},z^{(i)};\theta)}{{p(x^{(i)};\theta)}}\\&=p(z^{(i)}|x^{(i)};\theta) \end{aligned}$